package com.algorithm.dp;

import static java.lang.Integer.max;

public class MaxRectangle {
    public static void main(String[] args) {
        int[][] matrix = {
                {0, 1, 1, 1, 1},
                {1, 0, 1, 1, 1},
                {0, 0, 1, 1, 1},
                {1, 0, 0, 1, 0}
        };
        int max = maxRectangle(matrix);
        System.out.println(max);
    }

    /**
     * 每一行转化为直方图求矩形面积(下面的行忽略)
     * @param matrix
     * @return
     */
    public static int maxRectangle(int[][] matrix) {
        int[][] middle = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < middle[0].length; i++) {
            middle[0][i] = matrix[0][i];
        }

        for (int i = 1; i < middle.length; i++) {
            for (int j = 0; j < middle[0].length; j++) {
                middle[i][j] = matrix[i][j] == 0 ? 0 : middle[i - 1][j]+1;
                System.out.print(middle[i][j] + "\t");
            }
            System.out.println();
        }

        int max = 0;
        for (int i = 0; i < middle.length; i++) {
            int answer = MaxHistogram.getAnswer(middle[i]);
            max = max(max,answer);
        }
        return max;
    }


}
